﻿using System;
using System.Numerics;

namespace ProjectEulerIssues
{
	public partial class Program
	{
		[SolutionInfo(Links = "http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html, http://mukeshiiitm.wordpress.com/2010/03/23/project-euler-101/")]
		public static dynamic Problem101()
		{
			Func<BigInteger, BigInteger> Un = (BigInteger n) => 
			{
				var n2 = n * n;
				var n4 = n2 * n2;
				var n6 = n4 * n2;
				var n8 = n4 * n4;
				var n10 = n8 * n2;
				return (1 - n) * (1 + n2 + n4 + n6 + n8) + n10;
			};

			Func<int, BigInteger> calc = (int n) => 
			{
				BigInteger sm = 0;
				for (int i = 1; i < n; i++)
				{
					BigInteger nom = 1;
					BigInteger den = 1;
					for (int j = 1; j < n; j++)
					{
						if (i == j)
						{
							continue;
						}
						nom *= (n - j);
						den *= (i - j);
					}
					sm += (nom * Un(i) / den);
				}
				return sm;
			};

			Func<BigInteger> solve = () => 
			{
				BigInteger BopSum = 0;
				for (int i = 2; ; i++)
				{
					var ans = calc(i);
					if (ans == Un(i))
					{
						break;
					}
					else
					{
						BopSum += ans;
					}
				}
				return BopSum;
			};
			return solve();
		}
	}
}
